package com.apkcore.bl;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/sort-characters-by-frequency/
 */
public class _451根据字符出现频率排序 {
    public String frequencySort2(String s) {
        if (s == null) {
            return "";
        }
        char[] chars = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char aChar : chars) {
            map.put(aChar, map.getOrDefault(aChar, 0) + 1);
        }
        // 以v为基准的最大堆
        PriorityQueue<Node> q = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o2.v != o1.v) {
                    return o2.v - o1.v;
                }
                return o1.c - o2.c;
            }
        });
        for (char c : map.keySet()) {
            q.add(new Node(c, map.get(c)));
        }
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            Node poll = q.poll();
            int k = poll.v;
            while (k-- > 0) {
                sb.append(poll.c);
            }
        }

        return sb.toString();
    }

    class Node {
        char c;
        int v;

        Node(char _c, int _v) {
            c = _c;
            v = _v;
        }
    }


    /**
     * 直接使用数组来模拟
     */
    public String frequencySort(String s) {
        if (s == null) {
            return "";
        }
        char[] chars = s.toCharArray();
        // 128个字符，两个位置来表示属于，0位表示字符，1表示数量
        int[][] cnts = new int[128][2];
        // 初始化
        for (int i = 0; i < 128; i++) {
            cnts[i][0] = i;
        }
        for (char c : chars) {
            cnts[c][1] += 1;
        }
        Arrays.sort(cnts, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] != o2[1]) {
                    return o2[1] - o1[1];
                }
                return o1[0] - o2[0];
            }
        });
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 128; i++) {
            int k = cnts[i][1];
            if (k != 0) {
                while (k-- > 0) {
                    sb.append((char) cnts[i][0]);
                }
            }
        }

        return sb.toString();
    }
}
